 |
    |
A Polynomial Upper Bound for a Mutation-Based Algorithm on the Two-Dimensional Ising Model
Simon Fischer
FB Informatik, LS2, Univ. Dortmund, 44221 Dortmund, Germanysimon.fischer@cs.uni-dortmund.de
Abstract. Fitness functions based on the Ising model are suited excellently for studying the adaption capabilities of randomised search heuristics. The one-dimensional Ising model was considered a hard problem for mutation-based algorithms, and the two-dimensional Ising model was even thought to amplify the difficulties. While in one dimension the Ising model does not have any local optima, in two dimensions it does. Here we prove that a simple search heuristic, the Metropolis algorithm, optimises on average the two-dimensional Ising model in polynomial time.
Keywords: Ising model, expected optimisation time, adaption
LNCS 3102, p. 1100 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004